//! 页面替换器相关逻辑
//!

use std::ptr::NonNull;

use super::FrameID;

/// 链表节点
#[allow(dead_code)]
struct LinkNode<T> {
    /// 链表节点的内容
    v: T,

    /// 指向下一个链表节点的指针
    next: Option<NonNull<Self>>,

    /// 指向前一个链表节点的指针
    prev: Option<NonNull<Self>>,
}

/// 链表
struct LinkList<T> {
    /// 指向链表头节点的指针
    head: Option<NonNull<LinkNode<T>>>,

    /// 指向链表尾节点的指针
    tail: Option<NonNull<LinkNode<T>>>,
}

impl<T> LinkList<T> {
    pub fn new() -> Self {
        Self {
            head: None,
            tail: None,
        }
    }

    #[allow(unused)]
    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    #[allow(unused)]
    pub fn push_back(&mut self, v: T) -> NonNull<LinkNode<T>> {
        let node: NonNull<LinkNode<T>> = Box::leak(Box::new(LinkNode::<T> {
            v,
            prev: self.tail,
            next: None,
        }))
        .into();

        if let Some(mut h) = self.tail {
            unsafe {
                h.as_mut().next = Some(node);
            }
        } else {
            self.head = Some(node);
        }
        self.tail = Some(node);
        node
    }

    pub fn pop_back(&mut self) -> Option<T> {
        if let Some(h) = self.tail {
            let node = unsafe {
                let out = Box::from_raw(h.as_ptr());
                self.tail = out.prev;
                if let Some(mut prev) = out.prev {
                    prev.as_mut().next = None;
                } else {
                    self.head = None;
                };
                out
            };
            Some(node.v)
        } else {
            None
        }
    }

    pub fn push_front(&mut self, v: T) -> NonNull<LinkNode<T>> {
        let node: NonNull<LinkNode<T>> = Box::leak(Box::new(LinkNode::<T> {
            v,
            prev: None,
            next: self.head,
        }))
        .into();

        if let Some(mut h) = self.head {
            unsafe {
                h.as_mut().prev = Some(node);
            }
        } else {
            self.tail = Some(node);
        }
        self.head = Some(node);
        node
    }

    pub unsafe fn erase(&mut self, pos: NonNull<LinkNode<T>>) -> T {
        let node = Box::from_raw(pos.as_ptr());

        if let Some(mut prev) = node.prev {
            prev.as_mut().next = node.next;
        }

        if let Some(mut next) = node.next {
            next.as_mut().prev = node.prev;
        }

        if pos == self.head.expect("erase from empty link list") {
            self.head = None;
        }

        if pos == self.tail.expect("erase from empty link list") {
            self.tail = None;
        }
        node.v
    }
}

impl<T> Drop for LinkList<T> {
    fn drop(&mut self) {
        while self.tail.is_some() {
            self.pop_back();
        }
    }
}

/// 基于LRU的页框替换器
pub(crate) struct LRUReplacer {
    /// 缓存链表头.
    cache_list: LinkList<FrameID>,

    /// 从页框到缓存项的映射.
    cache_map: Vec<Option<NonNull<LinkNode<FrameID>>>>,

    /// 当前存在的缓存项
    sz: usize,
}

impl LRUReplacer {
    pub fn new(max_size: u32) -> Self {
        let cache_map = vec![None; max_size as usize];
        Self {
            cache_list: LinkList::new(),
            cache_map,
            sz: 0,
        }
    }

    pub fn add_cache(&mut self, frame: FrameID) {
        if self.cache_map[frame as usize].is_some() {
            return;
        }

        let iter = self.cache_list.push_front(frame);
        self.sz += 1;
        self.cache_map[frame as usize] = Some(iter);
    }

    pub fn victim(&mut self) -> Option<FrameID> {
        let out = self.cache_list.pop_back();
        if let Some(out) = out {
            self.cache_map[out as usize] = None;
            self.sz -= 1;
        }
        out
    }

    pub fn clean_cache(&mut self, frame: FrameID) -> bool {
        if let Some(pos) = self.cache_map[frame as usize] {
            unsafe {
                self.cache_list.erase(pos);
            }
            self.cache_map[frame as usize] = None;
            self.sz -= 1;
            true
        } else {
            false
        }
    }

    pub fn len(&self) -> usize {
        self.sz
    }

    pub fn capacity(&self) -> usize {
        self.cache_map.len()
    }
}
